Databases are used for various purposes. In medium-scale or large-scale systems, relational databases (RDB) that can eliminate logical contradictions are mainly used. Since an RDB fundamentally includes an entry and its value, and a pointer to the value of another entry associated with the former value, it is not easy to convert the RDB to a tree structure. Particularly when a large volume of data must be handled, many relations occur in the RDB. The volume of data significantly increases and the processing is time-consuming.
On the other hand, object-oriented databases such as XML database are proposed. This object-oriented database first saves data in a tree structure and enables sequential tracing of the branches of the tree.
However, in the tree structure of the conventional database has the following problems.
(1) The Root is Fixed.
Since the conventional tree structure includes a pointer from a specified node to another specified node, it is possible to change the link between nodes. Also, the pointer can only trace in one direction. Therefore, while logically, any element of the tree may be its root, the root is actually fixed.
(2) The Tree Structure is Fixed.
Each node has various attributes. For example, in the case where entries of office address and home address exist, a tree based on the office address (for example, Japan—Tokyo—Minato Ward . . . ) and a tree based on the home address (for example, Japan—Kanagawa Prefecture—Yokohama City . . . ) constitute logically separate trees. However, in the tree structure of the conventional database, it is impossible to construct these separate trees.
(3) The Processing Speed is Very Low, and Sorting and Totaling are Difficult.
Search processing takes a very long processing time because the tree must be traced sequentially. Also, since the tree must be similarly traced sequentially to specify an element, sorting and totaling are difficult.
Meanwhile, the present inventor has invented a technique of dividing table-format data into one or more information blocks, each containing a value list in which entry values belonging to specified entries are stored in order of entry value numbers corresponding to the entry values and a pointer array in which pointer values for indicating the entry value numbers are stored in univocal order of record numbers, and then sequentially tracing the record numbers, elements (pointer values) situated at positions in the pointer array corresponding to the record numbers, and elements (entry values) situated at positions in the value list indicated by the pointer values, thereby specifying the entry values corresponding to the record numbers, as described in the pamphlet of International Publication WO00/10103 (FIG. 3 and FIG. 4)
By employing such a data format, it is possible to realize search, totaling, sorting and the like at a very high speed, compared with the conventional RDB.
The present inventor has also proposed a technique of joining plural tables that employ the above-described data format, as disclosed in JP-A-2000-339390 (pages 14 to 17, and FIGS. 10 to 18).
This makes it possible to join plural tables by using entries having a common entry value as keys, and to easily realize search and totaling of the join tables.
Knowing that one or more tree structures can be constructed by utilizing the techniques disclosed in International Publication WO00/10103 and JP-A-2000-339390, the present inventor has realized this. According to this method and program, the above-described problems (1) to (3) are solved and a tree structure containing various entries can be constructed from an arbitrary root. Also, the processing speed is high, and totaling and sorting can be realized.
In short, it is an object of this invention to provide a method and program that makes it possible to select an arbitrary root, construct one or more desired tree structures at a high speed, and execute search, totaling and sorting at a high speed.